class Lzss {
  static N = 4096;
  static F = 18;
  static THRESHOLD = 2;
  static NIL = this.N;

  static textsize = 0;
  static codesize = 0;
  static printcount = 0;
  static text_buf = [];
  static match_position;
  static match_length;
  static lson = []
  static rson = []
  static dad = [];

  constructor() {
    Lzss.lson = new Array(Lzss.N + 1);
    Lzss.rson = new Array(Lzss.N + 257);
    Lzss.dad = new Array(Lzss.N + 1);
    Lzss.text_buf = new Array(Lzss.N + Lzss.F - 1);
  }

  static InitTree() {
    let i;
    Lzss.textsize = 0;
    Lzss.codesize = 0;
    Lzss.printcount = 0;
    for (i = Lzss.N + 1; i <= Lzss.N + 256; i++) Lzss.rson[i] = Lzss.NIL;
    for (i = 0; i < Lzss.N; i++) Lzss.dad[i] = Lzss.NIL;
  }

  static InsertNode(r) {
    let i, p, cmp;

    cmp = 1;
    p = Number(Lzss.N + 1 + Lzss.text_buf[r]);
    Lzss.rson[r] = Lzss.NIL;
    Lzss.lson[r] = Lzss.NIL;
    Lzss.match_length = 0;
    for (; ;) {
      if (cmp >= 0) {
        if (Lzss.rson[p] != Lzss.NIL) {
          p = Lzss.rson[p];
        } else {
          Lzss.rson[p] = r;
          Lzss.dad[r] = p;
          return;
        }
      } else {
        if (Lzss.lson[p] != Lzss.NIL) {
          p = Lzss.lson[p];
        } else {
          Lzss.lson[p] = r;
          Lzss.dad[r] = p;
          return;
        }
      }

      for (i = 1; i < Lzss.F; i++) {
        if ((cmp = Lzss.text_buf[r + i] - Lzss.text_buf[p + i]) != 0) break;
      }
      if (i > Lzss.match_length) {
        Lzss.match_position = p;
        if ((Lzss.match_length = i) >= Lzss.F) break;
      }
    }
    Lzss.dad[r] = Lzss.dad[p];
    Lzss.lson[r] = Lzss.lson[p];
    Lzss.rson[r] = Lzss.rson[p];
    Lzss.dad[Lzss.lson[p]] = r;
    Lzss.dad[Lzss.rson[p]] = r;
    if (Lzss.rson[Lzss.dad[p]] == p) Lzss.rson[Lzss.dad[p]] = r;
    else Lzss.lson[Lzss.dad[p]] = r;
    Lzss.dad[p] = Lzss.NIL;
  }


  static DeleteNode(p) {
    let q;

    if (Lzss.dad[p] == Lzss.NIL) return;
    if (Lzss.rson[p] == Lzss.NIL) q = Lzss.lson[p];
    else if (Lzss.lson[p] == Lzss.NIL) q = Lzss.rson[p];
    else {
      q = Lzss.lson[p];
      if (Lzss.rson[q] != Lzss.NIL) {
        do { q = Lzss.rson[q]; } while (Lzss.rson[q] != Lzss.NIL);
        Lzss.rson[Lzss.dad[q]] = Lzss.lson[q];
        Lzss.dad[Lzss.lson[q]] = Lzss.dad[q];
        Lzss.lson[q] = Lzss.lson[p];
        Lzss.dad[Lzss.lson[p]] = q;
      }
      Lzss.rson[q] = Lzss.rson[p];
      Lzss.dad[Lzss.rson[p]] = q;
    }
    Lzss.dad[q] = Lzss.dad[p];
    if (Lzss.rson[Lzss.dad[p]] == p) Lzss.rson[Lzss.dad[p]] = q; else Lzss.lson[Lzss.dad[p]] = q;
    Lzss.dad[p] = Lzss.NIL;
  }

  static byte(value) {
    return ((((value | 0) & 0xff) + 128) % 256) - 128;
  }

  Encode(ibuf, istart, isize, obuf, ostart) {
    let i, c, len, r, s, last_match_length, code_buf_ptr;
    let code_buf = new Array(17);
    let mask;
    let x, x1;

    x = x1 = 0;
    Lzss.InitTree();
    code_buf[0] = 0;
    code_buf_ptr = mask = 1;
    s = 0;
    r = Lzss.N - Lzss.F;
    for (i = s; i < r; i++) Lzss.text_buf[i] = ' ';
    for (len = 0, c = 0; len < Lzss.F && c < isize; len++, c++) {
      if (ibuf[istart + x] >= 0)
        Lzss.text_buf[r + len] = ibuf[istart + x];
      else
        Lzss.text_buf[r + len] = 0x100 + ibuf[istart + x];
      x++;
    }
    if ((Lzss.textsize = len) == 0) return 0;
    for (i = 1; i <= Lzss.F; i++) {
      Lzss.InsertNode(r - i);
    }
    Lzss.InsertNode(r);

    do {
      if (Lzss.match_length > len) Lzss.match_length = len;
      if (Lzss.match_length <= Lzss.THRESHOLD) {
        Lzss.match_length = 1;
        code_buf[0] |= mask;
        code_buf[code_buf_ptr++] = Lzss.text_buf[r];
      } else {
        code_buf[code_buf_ptr++] = Lzss.match_position & 0xff;
        code_buf[code_buf_ptr++] = ((((Lzss.match_position >> 4) & 0xf0) | (Lzss.match_length - (Lzss.THRESHOLD + 1))) & 0xff);
      }
      mask <<= 1;
      mask &= 0xff;
      if (mask == 0) {
        if (Lzss.codesize + code_buf_ptr > isize) return 0;
        for (i = 0; i < code_buf_ptr; i++) {
          obuf[ostart + x1] = Lzss.byte(code_buf[i]);
          x1++;
        }
        Lzss.codesize += code_buf_ptr;
        code_buf[0] = 0;
        code_buf_ptr = mask = 1;
      }
      last_match_length = Lzss.match_length;
      for (i = 0; i < last_match_length && c < isize; i++, c++) {
        Lzss.DeleteNode(s);
        if (ibuf[istart + x] >= 0)
          Lzss.text_buf[s] = ibuf[istart + x];
        else
          Lzss.text_buf[s] = 0x100 + ibuf[istart + x];
        if (s < Lzss.F - 1) {
          if (ibuf[istart + x] >= 0)
            Lzss.text_buf[s + Lzss.N] = ibuf[istart + x];
          else
            Lzss.text_buf[s + Lzss.N] = 0x100 + ibuf[istart + x];
        }
        s = (s + 1) & (Lzss.N - 1);
        r = (r + 1) & (Lzss.N - 1);
        Lzss.InsertNode(r);
        x++;
      }
      while (i++ < last_match_length) {
        Lzss.DeleteNode(s);
        s = (s + 1) & (Lzss.N - 1);
        r = (r + 1) & (Lzss.N - 1);
        len--;
        if (len > 0) Lzss.InsertNode(r);
      }
    } while (len > 0);
    if (code_buf_ptr > 1) {
      for (i = 0; i < code_buf_ptr; i++) {
        obuf[ostart + x1] = Lzss.byte(code_buf[i] & 0xff);
        x1++;
      }
      Lzss.codesize += code_buf_ptr;
    }
    return x1;
  }
}


module.exports = {
  Lzss
}

